Ant Colony Optimisation (ACO) is an effective population-based meta-heuristicfor the solution of a wide variety of problems. As a population-basedalgorithm, its computation is intrinsically massively parallel, and it isthere- fore theoretically well-suited for implementation on Graphics ProcessingUnits (GPUs). The ACO algorithm comprises two main stages: Tour constructionand Pheromone update. The former has been previously implemented on the GPU,using a task-based parallelism approach. However, up until now, the latter hasalways been implemented on the CPU. In this paper, we discuss severalparallelisation strategies for both stages of the ACO algorithm on the GPU. Wepropose an alternative data-based parallelism scheme for Tour construction,which fits better on the GPU architecture. We also describe novel GPUprogramming strategies for the Pheromone update stage. Our results show a totalspeed-up exceeding 28x for the Tour construction stage, and 20x for Pheromoneupdate, and suggest that ACO is a potentially fruitful area for future researchin the GPU domain.
展开▼
